Thực đơn
Thuật_toán_Grover Vòng lặp đầu tiênTừ định nghĩa, ta có bước khởi tạo
U s = 2 | s ⟩ ⟨ s | − I {\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I} ,Uω có thể được biểu diễn theo cách:
U ω = I − 2 | ω ⟩ ⟨ ω | {\displaystyle U_{\omega }=I-2\left|\omega \right\rangle \left\langle \omega \right|} .Các bước sau cho thấy những gì xảy ra trong vòng lặp đầu tiên: ⟨ ω | s ⟩ = ⟨ s | ω ⟩ = 1 N {\displaystyle \langle \omega |s\rangle =\langle s|\omega \rangle ={\frac {1}{\sqrt {N}}}} .
⟨ s | s ⟩ = N 1 N ⋅ 1 N = 1 {\displaystyle \langle s|s\rangle =N{\frac {1}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}=1} . U ω | s ⟩ = ( I − 2 | ω ⟩ ⟨ ω | ) | s ⟩ = | s ⟩ − 2 | ω ⟩ ⟨ ω | s ⟩ = | s ⟩ − 2 N | ω ⟩ {\displaystyle U_{\omega }|s\rangle =(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle } . U s ( | s ⟩ − 2 N | ω ⟩ ) = ( 2 | s ⟩ ⟨ s | − I ) ( | s ⟩ − 2 N | ω ⟩ ) = 2 | s ⟩ ⟨ s | s ⟩ − | s ⟩ − 4 N | s ⟩ ⟨ s | ω ⟩ + 2 N | ω ⟩ = {\displaystyle U_{s}(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=(2|s\rangle \langle s|-I)(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=2|s\rangle \langle s|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}|s\rangle \langle s|\omega \rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle =} = 2 | s ⟩ − | s ⟩ − 4 N ⋅ 1 N | s ⟩ + 2 N | ω ⟩ = | s ⟩ − 4 N | s ⟩ + 2 N | ω ⟩ = N − 4 N | s ⟩ + 2 N | ω ⟩ {\displaystyle =2|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle =|s\rangle -{\frac {4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle ={\frac {N-4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle } .Sau khi 2 toán tử ( U ω {\displaystyle U_{\omega }} and U s {\displaystyle U_{s}} ) được sử dụng, giá trị cần tìm đã tăng từ | ⟨ ω | s ⟩ | 2 = 1 / N {\displaystyle \left|\langle \omega |s\rangle \right|^{2}=1/N} đến | ⟨ ω | U s U ω s ⟩ | 2 ≈ 9 / N {\displaystyle \left|\langle \omega |U_{s}U_{\omega }s\rangle \right|^{2}\approx 9/N} .
Thực đơn
Thuật_toán_Grover Vòng lặp đầu tiênLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ thiên văn học Thuật ngữ lý thuyết đồ thị Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật toán Kruskal Thuật toán sắp xếpTài liệu tham khảo
WikiPedia: Thuật_toán_Grover http://www.amazon.com/Foundations-Quantum-Mechanic...